package com.zlk.algorithm.dataStructure.tree.treeBase;
import com.zlk.algorithm.dataStructure.tree.TreeNode;
import org.junit.Test;

import java.util.LinkedList;
import java.util.Stack;
/**
 * @program: algorithm
 * @ClassName UnRecursiveTraversalBT
 * @description:非递归实现二叉树的遍历
 * @author: slfang
 * @create: 2024-02-18 09:41
 * @Version 1.0
 **/
public class UnRecursiveTraversalBT {

    /**
     * 先序遍历
     */
    public void pre(TreeNode node){
        Stack<TreeNode> stack = new Stack<>();
        stack.add(node);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            System.out.println(pop.value);
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
    }

    public void mid(TreeNode cur){
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty()||cur!=null){
            if(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                System.out.println(cur.value);
                cur = cur.right;
            }
        }
    }

    public void post(TreeNode head){
        if (head != null) {
            Stack<TreeNode> s1 = new Stack<TreeNode>();
            Stack<TreeNode> s2 = new Stack<TreeNode>();
            s1.push(head);
            while (!s1.isEmpty()) {
                head = s1.pop(); // 头 右 左
                s2.push(head);
                if (head.left != null) {
                    s1.push(head.left);
                }
                if (head.right != null) {
                    s1.push(head.right);
                }
            }
            // 左 右 头
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().value + " ");
            }
        }
    }

    /**
     * LevelTraversalBT
     */
    public void LevelTraversalBT(TreeNode node){
        LinkedList<TreeNode> linkedList = new LinkedList();
        linkedList.add(node);
        while (!linkedList.isEmpty()){
            TreeNode pop = linkedList.poll();
            System.out.println(pop.value);
            if(pop.left!=null){
                linkedList.add(pop.left);
            }
            if(pop.right!=null){
                linkedList.add(pop.right);
            }
        }
    }


    @Test
    public void test(){
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(2);
        head.right = new TreeNode(3);
        head.left.left = new TreeNode(4);
        head.left.right = new TreeNode(5);
        head.right.left = new TreeNode(6);
        head.right.right = new TreeNode(7);

        pre(head);
        System.out.println("========");
        mid(head);
        System.out.println("========");
        post(head);
        System.out.println("=====level===");
        LevelTraversalBT(head);
//        pos2(head);
//        System.out.println("========");
    }




}
